package com.ming.learn.from.carl.string;

import static com.ming.commons.utils.KMPUtils.getNext;

/*
题目：28. 实现 strStr()
 */
public class Of20201228LeetCode28 {
    /*
    给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
    示例 1:
    输入: haystack = "hello", needle = "ll"
    输出: 2
    示例 2:
    输入: haystack = "aaaaa", needle = "bba"
    输出: -1
    说明:
    当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
    对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
     */
    public static void main(String[] args) {
        System.out.println(strStr("aabaabaaf", "aabaaf"));
    }
    /*
    暴力解法
    时间复杂度O(m*n)
    代码略
     */

    /*
    KMP算法
    时间复杂度O(m+n)
     */
    private static int strStr(String haystack, String needle) {
        if (needle.length() == 0)
            return 0;
        int[] next = getNext(needle);
        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1]; // 这里要找j前一位的对应的回退位置了
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == needle.length()) {
                return (i - needle.length() + 1);
            }
        }
        return -1;
    }

    /*
        private static int[] getNext(String s) {
        int[] next = new int[s.length()];
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(i) != s.charAt(j)) { // j要保证大于0，因为下面有取j-1作为数组下表的操作
                j = next[j - 1]; // 注意这里，是要找前一位的对应的回退位置了
            }
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
     */
}
